package com.chj.chuji.tijie08;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Household {

	public static class Node {
		public int index;
		public int p;

		public Node(int index, int p) {
			this.index = index;
			this.p = p;
		}

		public Node() {
		}
	}

	public static class NodeComparator implements Comparator<Node> {

		@Override
		public int compare(Node o1, Node o2) {
			if (o1.p < o2.p) {
				return 1;
			} else if (o1.p > o2.p) {
				return -1;
			}
			return 0;
		}

	}

	public static void main(String[] args) {
		int N = 100005;

		PriorityQueue<Node> q = new PriorityQueue<>(new NodeComparator());
		PriorityQueue<Node> q1 = new PriorityQueue<>(new NodeComparator());

		int[] s = new int[N];
		int[] a = new int[N];
		int n = 5;

		int res = 0;
		int[] srd = new int[] { 1, 2, 3, 4, 5 };
		for (int i = 1; i <= n; i++) {
			s[i] = srd[i - 1];
		}

		int[] ard = new int[] { 1, 2, 3, 4, 5 };
		for (int i = 1; i <= n; i++) {
			a[i] = ard[i - 1];

			Node x = new Node();
			x.index = i;
			x.p = a[i];

			Node y = new Node();
			y.index = i;
			y.p = s[i] * 2 + a[i];

			q.add(x);
			q1.add(y);
		}

		/// 第一个用户输出最大的那个
		int index;
		int m_l;
		/// 取出q1最大的那一个
		Node y = q1.peek();
		q1.poll();
		index = y.index;
		res = y.p;
		m_l = s[index];
		s[index] = 0;
		a[index] = 0;
//      cout << res << endl;
//      x.index = y.index = 0;
		Node x = new Node();
		x.index = 0;
		y.index = 0;
		for (int i = 2; i <= n; i++) {
			while (q.size() > 0 && (s[x.index] == 0)) {
				x = q.peek();
				q.poll();
			}
			while (q1.size() > 0 && s[y.index] == 0) {
				y = q1.peek();
				q1.poll();
				if (y.index < index)
					y.index = 0;
			}
			/*
			 * while(q.size()>0) { ///找最大的疲劳值 x = q.top(); if(s[x.index] != 0) { q.pop();
			 * break; } q.pop();
			 * 
			 * } while(q1.size()>0) { ///找记录距离*2 + P最大 y = q1.top(); if(s[y.index] !=
			 * 0&&y.index >= index) { q1.pop(); break; } q1.pop();
			 * 
			 * }
			 */

			int xx = x.p;
			int yy = a[y.index] + 2 * (s[y.index] - m_l);
			// cout << "index:" << y.index << endl;
			// cout <<"aaaa" << xx << "===" << yy <<endl;
			if (xx >= yy) {
				res += xx;
				s[x.index] = 0;

			} else {
				res += yy;
				m_l = s[y.index];
				s[y.index] = 0;
				index = Math.max(y.index, index);
			}

			System.out.println(res);
		}
	}
}
//	#include<bits/stdc++.h>
//	using namespace std;#
//	define N 100005
//	struct node{
//	int index, p;/// i代表第几个村庄，p代表疲劳值
//	bool operator<(node x)const
//	{
//		return p < x.p;/// 按照疲劳值从大到小排序
//	}}x,y;
//	priority_queue<node> q, q1;/// q是记录疲劳值，q1是记录距离*2 + P
//	int s[N],a[N];
//	int n;
//
//int main()
//{
//    while(cin >> n)
//    {
//        int res = 0;
//        for(int i = 1; i <= n; i ++)
//        {
//            cin >> s[i];
//        }
//        for(int i = 1; i <= n; i ++)
//        {
//            cin >> a[i];
//
//            x.index = i;
//            x.p = a[i];
//
//            y.index = i;
//            y.p = s[i]*2 + a[i];
//
//            q.push(x);
//            q1.push(y);
//        }
//
//        ///第一个用户输出最大的那个
//        int index;
//        int m_l;
//        ///取出q1最大的那一个
//        y = q1.top(), q1.pop();
//        index = y.index;
//        res = y.p;
//        m_l = s[index];
//        s[index] = 0;
//        a[index] = 0;
//        cout << res << endl;
//        x.index = y.index = 0;
//        for(int i = 2; i <= n; i ++)
//        {
//            while(q.size() && s[x.index] == 0){
//                x = q.top(),q.pop();
//            }
//              while(q1.size() && s[y.index] == 0){
//                y = q1.top(),q1.pop();
//                if(y.index < index) y.index = 0;
//            }
//            /*
//            while(q.size()>0)
//            {
//                ///找最大的疲劳值
//                x = q.top();
//                if(s[x.index] != 0)
//                {
//                    q.pop();
//                    break;
//                }
//                q.pop();
//
//            }
//            while(q1.size()>0)
//            {
//                ///找记录距离*2 + P最大
//                y = q1.top();
//                if(s[y.index] != 0&&y.index >= index)
//                {
//                    q1.pop();
//                    break;
//                }
//                q1.pop();
//
//            }
//            */
//
//            int xx = x.p;
//            int yy = a[y.index] + 2 *(s[y.index] - m_l);
//          //cout << "index:" << y.index << endl;
//            //cout <<"aaaa" << xx << "===" << yy <<endl;
//            if(xx >= yy)
//            {
//                res += xx;
//                s[x.index] = 0;
//
//            }
//            else
//            {
//                res += yy;
//                m_l = s[y.index];
//                s[y.index] = 0;
//                index = max(y.index,index);
//            }
//            cout << res << endl;
//
//        }
//    }
//    return 0;
//}
